package T879;

public class Main {
}


class Solution {
    public static void main(String[] args) {
        int[] group = {2, 2, 2, 2, 2};
        int[] profit = {1, 2, 1, 1, 0};
        System.out.println(profitableSchemes(1, 1, group, profit));
    }

    static final int MOD = 1000000007;
    public static int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][][] dp = new int[n+1][minProfit+1][group.length];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= minProfit; j++) {
                for (int k = 0; k < group.length; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        return f2(n, minProfit, group, profit, 0, dp);
    }
    public static int f2(int n, int Profit, int[] group, int[] profit, int i, int[][][] dp) {
        //没有员工了
        if (n <= 0) {
            return Profit <= 0 ? 1 : 0;
        }
        //没有方案了
        if (i == group.length) {
            return Profit <= 0 ? 1 : 0;
        }
        if(dp[n][Profit][i]!=-1) {
            return dp[n][Profit][i];
        }
        //舍弃当前的方案
        int p1 = f2(n, Profit, group, profit, i + 1, dp);
        int p2 = 0;
        //保留当前的方案
        if(n>=group[i]) {
            p2 = f2(n - group[i], Math.max(Profit - profit[i], 0), group, profit, i + 1, dp);
        }
        dp[n][Profit][i] = (int)((long)(p1 + p2)%MOD);
        return dp[n][Profit][i];
    }


    /**
     * @param n      剩余员工数
     * @param Profit 还差多少钱满足利润
     * @param group
     * @param profit
     * @param i      走到第几个方案
     * @return
     */
    public static int f1(int n, int Profit, int[] group, int[] profit, int i) {
        //没有员工了
        if (n <= 0) {
            return Profit <= 0 ? 1 : 0;
        }
        //没有方案了
        if (i == group.length) {
            return Profit <= 0 ? 1 : 0;
        }
        //舍弃当前的方案
        int p1 = f1(n, Profit, group, profit, i + 1);
        int p2 = 0;
        //保留当前的方案
        if(n>=group[i]) {
            p2 = f1(n - group[i], Profit - profit[i], group, profit, i + 1);
        }
        return p1 + p2;
    }
}